package com.leetcode.二叉树.深度优先.递归遍历;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

/**
 * Recursive:递归
 * Traversal:遍历
 *	二叉树的递归遍历有三种：前、中、后序遍历，前中后是对于中间节点来说的 。
 *	遍历顺序：
 *	前序遍历：中->左->右
 *	中序遍历：左->中->右
 *	后序遍历：左->右->中
 *
 *	二叉树的每一个节点都可以看成是中间节点，只不过是有没有左右子树的区别而已。二叉树的所有遍历算法都是利用这个来实现的！！！！！！！！！
 */
public class RecursiveTraversal {
	/**
	 * 前序遍历
	 */
	public List<Integer> preorderTraversal(TreeNode root) {
		List<Integer> result = new ArrayList<>();
		preorder(root, result);
		return result;
    }
	public void preorder(TreeNode node,List<Integer> result) {
		if(node == null) return ;
		result.add(node.val);//中间节点先访问
		preorder(node.left, result);//遍历左子树
		preorder(node.right, result);//遍历右子树
	}
	
	/**
	 * 中序遍历
	 */
	 public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> result = new ArrayList<>();
		inorder(root, result);
		return result;
	 }
	 public void inorder(TreeNode node,List<Integer> result) {
		if(node == null) return ;
		inorder(node.left, result);//先访问左子树
		result.add(node.val);//在访问中间节点
		inorder(node.right, result);//最后访问右子树
	 }
	 
	 /**
	  * 后序遍历
	  */
	 public List<Integer> postorderTraversal(TreeNode root) {
		List<Integer> result = new ArrayList<>();
		postorder(root, result);
		return result;
	 }
	 public void postorder(TreeNode node,List<Integer> result) {
		 if(node == null) return ;
		 postorder(node.left,result);//先访问左子树
		 postorder(node.right,result);//再访问右子树
		 result.add(node.val);//最后访问中间节点
	 }
}
//树的定义
class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode() {
	}

	TreeNode(int val) {
		this.val = val;
	}

	TreeNode(int val, TreeNode left, TreeNode right) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}